package 回溯算法;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: biubiu0002
 * @Date: 2021-09-16 22:26
 **/
public class 单词搜索Ⅱ {
    public final static int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private int row, col;
    private List<String> res = new ArrayList();
    // [["o","a","b","n"],["o","t","a","e"],["a","h","k","r"],["a","f","l","v"]]
    // ["oa","oaa"]
    public static void main(String[] args) {
        char[][] board = {{'o','a','b','n'},{'o','t','a','e'},{'a','h','k','r'},{'a','f','l','v'}};
        String[] words = {"oa","oaa"};
        System.out.println(new 单词搜索Ⅱ().findWords(board, words));
    }

    public List<String> findWords(char[][] board, String[] words) {
        row = board.length;
        col = board[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                for (String word : words) {
                    boolean[][] isUsed = new boolean[row][col];
                    if (backtrack(0,i,j,board,word,isUsed)) {
                        res.add(word);
                    }

                }

            }
        }
        return res;


    }


    public boolean backtrack(int curlen, int r, int c, char[][] board, String word, boolean[][] isUsed) {
        if (word.length() == curlen) {
            return true;
        }
        if (r < 0 || r >= row || c < 0 || c >= col || isUsed[r][c] || board[r][c] != word.charAt(curlen)) {
            return false;
        }
        isUsed[r][c] = true;
        for (int[] d : DIRECTIONS) {
            if (backtrack(curlen + 1, r + d[0], c = d[1], board, word, isUsed)) {
                return true;
            }

        }
        isUsed[r][c] = false;
        return false;


    }
}
